package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class code114 {

    public static class  TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    static List<TreeNode> list = new ArrayList<TreeNode>();

    public static void main(String[] args) {
        Integer[] arrayA = new Integer[]{0};
        TreeNode root = buildtree(arrayA);
        flatten(root);
    }

    public static void flatten(TreeNode root) {
        if (root != null){
            ToList(root);
            if(list.size() >=2){
                TreeNode first = root;
                for (int i = 1; i < list.size(); i++) {
                    first.right = list.get(i);
                    first.left = null;
                    first = first.right;
                }
            }
        }
    }

    private static void ToList(TreeNode root) {
        list.add(root);
        if (root.left !=null){
            ToList(root.left);
        }
        if (root.right != null){
            ToList(root.right);
        }
    }

    private static TreeNode buildtree(Integer[] arrayA) {
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode res = new TreeNode(arrayA[0]);
        queue.add(res);
        int i = 1;
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            if (i<arrayA.length && arrayA[i] != null){
                TreeNode treeNode = new TreeNode(arrayA[i]);
                poll.left = treeNode;
                queue.add(treeNode);
            }
            i++;
            if (i<arrayA.length && arrayA[i] != null){
                TreeNode treeNode = new TreeNode(arrayA[i]);
                poll.right = treeNode;
                queue.add(treeNode);
            }
            i++;
        }
        return res;
    }


}
